# next数组创建函数
def build_next(rna):
    next = [0]
    prefix_len = 0
    i = 1
    while i < len(rna):
        if rna[prefix_len] == rna[i]:
            prefix_len += 1
            next.append(prefix_len)
            i += 1
        else:
            if prefix_len == 0:
                next.append(0)
                i += 1
            else:
                prefix_len = next[prefix_len - 1]
    return next

# KMP主算法
# dna.len>=rna.len>0
def kmp_compare(dna, rna):
    next = build_next(rna)
    d = 0
    r = 0
    flag = False
    while d < len(dna):
        if dna[d] == rna[r]:  # 字符匹配
            d += 1
            r += 1
        elif r > 0:           # 字符失配，查询前一个字符对应next数组值
            r = next[r-1]
        else:                 # 首字符失配 dna[d] != rna[0]
            d += 1
        if r == len(rna):     # rna in dna
            flag = True
            return d-r        # 返回匹配字符串首字符索引
    if flag == False:         # rna not in dna
        return -1



